package tree;

import java.util.Comparator;

@SuppressWarnings("unchecked")
public class BST<E> extends BinaryTree<E> {
	private Comparator<E> comparator;

	public BST() {
		this(null);
	}

	public BST(Comparator<E> comparator) {
		this.comparator = comparator;
	}

	public void add(E element) {
		elementNotNullCheck(element);
		if (root == null) {
			root = createNode(element, null);
			size++;
			afterAdd(root);
			return;
		}
		Node<E> parent = null;
		Node<E> node = root;
		int cmp = 0;
		while (node != null) {
			parent = node;
			cmp = compare(element, node.element);
			if (cmp > 0) {
				node = node.right;
			} else if (cmp < 0) {
				node = node.left;
			} else {
				node.element = element;
				return;
			}
		}
		Node<E> newNode = createNode(element, parent);
		if (cmp > 0) {
			parent.right = newNode;
		} else {
			parent.left = newNode;
		}
		size++;
		afterAdd(newNode);
	}

	protected void afterAdd(Node<E> node) {

	}

	protected void afterRemove(Node<E> node) {
	}

	public void remove(E element) {
		remove(node(element));
	}

	private Node<E> node(E element) {
		Node<E> node = root;
		while (node != null) {
			int cmp = compare(element, node.element);
			if (cmp == 0)
				return node;
			if (cmp > 0) {
				node = node.right;
			} else { // cmp < 0
				node = node.left;
			}
		}
		return null;
	}

	public boolean contains(E element) {
		return false;
	}

	public void remove(Node<E> node) {
		if (node == null) {
			return;
		}
		size--;
		if (node.hasTwoChildren()) {
			Node<E> preNode = this.predecessor(node);
			node.element = preNode.element;// 把需要被删除的节点的element换成他的前驱节点的element，这时候只需要删除前驱节点不就完了吗？前驱节点是度为0/1的；
			node = preNode;// node指向前驱节点，后面删除node就等于删除前驱节点；现在node就是一个度为0或者1的节点，然后接下来执行删除度为0或者1的节点；
		}

		Node<E> replaceNode = node.left != null ? node.left : node.right;// 将要替换node的节点
		if (replaceNode != null) {// 替换的节点不为空 度为1
			replaceNode.parent = node.parent;
			if (node.parent == null) {
				root = replaceNode;
			} else {
				if (node.parent.left != null) {
					node.parent.left = replaceNode;
				} else {
					node.parent.right = replaceNode;
				}
			}
		} else if (node.parent == null) {// 替换的节点为空，并且父节点为空，只有他一个节点 度为0
			root = null;
			afterRemove(node);
		} else {// 替换的节点为空 度为0
			if (node.parent.left == node) {
				node.parent.left = null;
			} else {
				node.parent.right = null;
			}
			afterRemove(node);
		}

	}

	private int compare(E element1, E element2) {
		if (this.comparator != null) {
			return comparator.compare(element1, element2);
		}
		return ((Comparable<E>) element1).compareTo(element2);
	}

	public void elementNotNullCheck(E element) {
		if (element == null) {
			throw new IllegalArgumentException("element not be null");
		}
	}

}
